1. Field of the Invention
The present invention relates to a pattern extracting device, and more specifically to a pattern extracting device for extracting a pattern from a combination of various patterns such as straight lines, characters, drawings, etc. by retrieving characters and symbols stored not only in a hand-written character recognizing device but also in a printed character recognizing device and a figure recognizing device, and by separating a line from an object, drawings from characters, etc.
That is, the present invention relates to, for example, a pattern extracting device for extracting a pattern such as a character, figure, etc. from the touching character box, line, etc. stored in the hand-written character recognizing device, for example, an optical character reader, etc.
2. Description of the Related Art
Recently, hand-written character recognizing devices have been demanded as hand-written character input/output devices. To correctly recognize an individual character in such hand-written character recognizing devices, it is important to correctly retrieve the character as a preprocess for recognizing the character.
Characters are recognized in a document in which character positions, areas, etc. are initially specified in a list, table, etc. In such a document, boxes are initially printed to indicate the positions of letters not in drop-out color but in non-drop-out color such as the same color as that of the letters or deep color. As a result, in a document printed in non-drop-out color, characters can be automatically recognized at a high recognition rate only if they are written neatly so that they are contained wi the specified area of input characters identified by black-frame boxes. However, if they are written on or over the specified areas or touching the lines identifying input character positions, then the recognition rate is considerably lowered.
Therefore, to improve the recognition rate, only the characters, drawings, symbols, etc. should be extracted from the characters touching the lines, boxes, etc. for correct retrieval in list, table, etc. where character positions are identified by non-drop-out color.
The Applicant of the present invention disclosed the first image extracting system shown in FIG. 1 in Tokugan-hei 5-103257 filed with the Patent Office of Japan. The input pattern to be processed in this system is a binary image corrected to remove extreme obliqueness, turn, etc., and preprocessed to remove noises, low spots, etc. Thus, the character boxes are removed from, for example, the lists and tables with deep-color character boxes based on the input pattern. For example, a plurality of one-row character boxes are provided. Some of the boxes are not defined for size, position, or obliqueness. When characters are hand-written to these boxes, only the boxes can be removed even if the characters are touching the boxes or partially overlap the lines.
As shown in FIG. 1, the first image extracting system comprises a link pattern extracting unit 1, a line detecting unit 2, a straight line detecting unit 3, a box detecting unit 4, and a box separating unit 5. The link pattern extracting unit 1 extracts a link pattern in which picture elements are connected from an input pattern comprising a straight-line portion comprising boxes, lines, etc., and graphics, characters, or symbols. The line detecting unit 2 contains a fine-line process and detects a broken line or a part of a straight line for predetermined length in a link pattern. The straight line detecting unit 3 detects a long straight line by integrating the obtained broken lines or a part of the straight line. The box detecting unit 4 extracts a straight line forming part of a character box by recognizing, for example, the space between the obtained straight lines. The box separating unit 5 obtains the intersection of the extracted straight lines, divides the character box into a plurality of smaller character boxes each containing a single character according to the intersection information, and calculates the thinness of the line forming the smaller character boxes. Then, the character box is separated from the link pattern based on the thinness of the line forming the character box.
When the character box to be removed from the input pattern is a box other than the above described character box, such character box extracting methods as those disclosed by Tokukai-sho 62-212888, Tokukai-hei 3-126186, are also proposed. In these character box extracting methods, the format information relating to the position, size, etc. and other information about obliqueness are input and stored as listing data. The character boxes are removed based on the stored information.
In addition to the first image extracting system, the Applicant of the present invention also disclosed the second image extracting system in Tokukai-hei 6-309498 filed with the Patent Office of Japan to extract only characters from those touching character boxes.
FIG. 2 is a block diagram showing the entire configuration of this system.
In FIG. 2, a character box extracting unit 11 extracts only the character box from the binary image of the characters touching their character box (line-touching characters), and removes the character box.
In this process, the line-touching portion of a line forming part of the line-touching character indicates a low spot, thereby showing broken lines in the line forming part of the character.
For example, the binary image of "3" linked by the label 1 shown in FIG. 3A is divided into 3 broken lines forming part of the character as a result of the extraction and removal of a character box 21 as shown in FIG. 3B. The 3 broken lines are assigned the labels 1, 2, and 3. The binary image of "7" linked by the label 1 shown in FIG. 4A is divided into 3 broken lines forming part of the character as a result of the extraction and removal of a character box 23 as shown in FIG. 4B. The 3 broken lines are assigned the labels 1, 2, and 3.
An interpolating unit 12 interpolates necessary elements after evaluating the geometrical structure, for example, the direction of and clearance between the lines which form part of a character and are assigned labels.
Thus, the binary image of "3" broken at its line-touching portion as shown in FIG. 3B can be supplemented, thereby completing the character "3" with label 1 as shown in FIG. 3C. The binary image of "7" broken at its line-touching portion as shown in FIG. 4B is supplemented. However, the necessary elements are interpolated only between the lines with labels 1 and 2 as shown in FIG. 4C, but not between the lines with labels 1 and 3. As a result, the character "7" remains divided as two broken lines with labels 1 and 2 as shown in FIG. 4C.
A re-interpolating unit 13 interpolates necessary elements into the broken lines forming part of a character when the character has a line just touching in parallel to the line forming the character box. In this process, the line-touching character is preliminarily extracted according to the linkage based on the labels assigned to the line-touching character, detects the coincidence of the pattern interpolated by the interpolating unit 12 with the above described linkage of the line-touching character, and re-interpolates the necessary line touching in parallel to the line forming the character box.
Thus, the binary image "7" divided into the two broken lines with labels 1 and 2 as shown in FIG. 4C can be completed into the character shown in FIG. 4D.
As a result, the line-touching character can be reconstructed by the interpolating unit 12 or re-interpolating unit 13 after removing the character box.
The supplemented and re-supplemented patterns output respectively by the interpolating unit 12 and re-interpolating unit 13 are input to a recognizing unit 14. The recognizing unit 14 contains a plurality of character category dictionaries, compares the supplemented or re-supplemented pattern with each of the category dictionaries, and outputs the code of the character category indicating the smallest difference from the supplemented or re-supplemented pattern. That is, in the example shown in FIG. 4, it is recognized that the pattern shown in FIG. 4C belongs to the character category of "". Likewise, it is recognized that the pattern shown in FIG. 4D belongs to the character category of "7". Then, it is determined that "7" indicates smaller difference, the character is finally recognized as "7", and the character code of 7 is output.
However, the first image extracting system disclosed by the present invention has the following problem, and therefore should be further improved. The first problem is that a character box cannot be successfully extracted when the character box is not to contain a single character or to contain a row of characters, that is, when the character box is designed for listings or in a free format. The second problem is that the line detecting unit 2 contains a fine-line process unit for performing a fine-line process, thereby taking a long process time. Furthermore, the fine-line process impairs the linearity of an original image. Therefore, if a fine-line process is performed on the original image of "6" partially overlapping the line forming the character box as shown in FIG. 5A, the output pattern indicates a combination of curves as shown in FIG. 5B. Since the character box cannot be detected as a straight line, it cannot be correctly extracted. The third problem is that a character box cannot be extracted when a character touches a plurality of adjacent lines forming the character box because, upon detection of broken lines, the character box is not recognized as a single-character box or a block-of-character box and the subsequent processes are aborted. The fourth problem is that a character box may not be correctly extracted after failing in searching for the character box if the search does not start at the correct start point because a partial pattern of the original image of the character box is traced to extract the character box.
The fourth problem is described below by referring to the example shown in FIG. 6. A partial pattern can be searched for downward. If the downward search has reached the bottom, then the search is made in the left or right direction by, for example, a predetermined number of picture elements corresponding to the thinness of the line forming the character box. Therefore, when the search starts at point A, the search is made in a good condition as shown in FIG. 26 by an arrow 26. However, if the search starts at point B, the search for a partial pattern cannot be made downward. Even if the search is then made in the left or right direction by the predetermined number of picture elements, the search cannot be successful using an arrow 27 shown in FIG. 6 because the partial pattern does not exist at the lower area. As a result, the character box cannot be extracted if the search starts at B.
In the character box extracting method disclosed by the publication of the above described Tokukai-sho 62-212888 and Tokukai-hei 3-126186, a character box can be extracted even if it is a block-of-character box in a table format. However, since the format information such as the position, size, obliqueness, etc. can be preliminarily entered and stored as listing data, the method has the problem that it is subject to have influences of the uneven surface made by the character box or of a slight obliqueness. Therefore, a character box slightly off a predetermined position can be recognized as a character and cannot be extracted as a character box. Otherwise, a character may be extracted as a part of the character box. Furthermore, since the user is required to enter the information for all character boxes in the listings, the entry process takes a long time and charges the user with a heavy load.
The above described second image extracting system has the following problems.
In this method, as described above, the recognizing unit 14 compares a supplemented pattern or a re-supplemented pattern with standard patterns entered in various types of character category dictionaries and outputs, as a recognition result, a character code indicating the smallest difference. In this example, the interpolating unit 12 or re-interpolating unit 13 respectively interpolates or re-interpolates necessary elements into the line-touching character. In fortunate cases, the broken lines forming part of a character can be supplemented based on the portion touching the character box. In unfortunate cases, however, the broken lines cannot be supplemented. FIG. 7 shows such examples.
As shown in FIG. 7A, the lower line of the character pattern "2" touches a character box 29 and the line-touching portion is almost completely on the character box 29. In this case, the character box extracting unit 11 removes the character box 29 as shown in FIG. 7B, and the character pattern of "2" is divided into the partial patterns with labels 1 and 2. Then, the interpolating unit 12 links the two partial patterns to make the pattern with label 1 as shown in FIG. 7C. Since the lower line forming the character "2" is not supplemented, there is the possibility that the recognizing unit 14 can recognize the pattern shown in FIG. 7C mistakenly as "7", but not "2".
If a part of the line-touching character is not written over line of the character box, but completely on the line, then the line-touching portion cannot be supplemented by the interpolating unit 12 or re-interpolating unit 13. As a result, it is almost impossible for the recognizing unit 14 to correctly recognize the line-touching character.
Therefore, for example, the optical character reading device of Tokukai-hei 3-122786 filed with the Patent Office of Japan has disclosed the system of recognizing a line-touching character using the dictionary by storing the partial patterns for a line-touching character or a character written over the character box after removing the character box. However, since a great number of the touching states can be assumed between a character and its character box, all the partial patterns for all characters cannot be stored. Improving the recognition rate refers to an increasing cost with the storage capacity for the dictionaries becoming extremely large. Furthermore, the improvement of the recognition rate is limited because the number of stored partial patterns is limited. With the increasing number of the partial patterns stored in the dictionaries, the access time to the dictionaries also increases, thereby lowering the recognition speed.
The optical character reading device of Tokukai-hei 6-62044 filed with the Patent Office of Japan has disclosed the system of recognizing a character by removing an underlined area or a character box area and comparing the character pattern with the binary pattern information about the standard characters in each character category stored in the dictionary. In this method, as shown by the examples in FIGS. 7A and 7B, a character cannot be correctly recognized if the line-touching portion is removed and the remaining character pattern is similar to another character category. In this system, the underlined area or character box area is removed when characters are recognized, but the portion of the character written over the character box is not supplemented. Therefore, if a character partially overlaps its character box, the recognition rate is lowered.